package com.lw.leetcode.node;

import java.util.ArrayList;
import java.util.List;

/**
 * 1530. 好叶子节点对的数量
 *
 * @Author liw
 * @Date 2021/5/21 16:45
 * @Version 1.0
 */
public class CountPairs {

    public static void main(String[] args) {
        CountPairs test = new CountPairs();
        int i = test.countPairs(TreeNode.getInstance(), 3);
        System.out.println(i);
    }

    int count = 0;
    public int countPairs(TreeNode root, int distance) {
        find(root, distance);
        return count;
    }

    public List<Integer> find(TreeNode node, int distance) {
        if (node == null) {
            return new ArrayList<>();
        }
        List<Integer> l = find(node.left, distance);
        List<Integer> r = find(node.right, distance);
        if (l.size() == 0 && r.size() == 0) {
            l.add(1);
            return l;
        }
        for (Integer a : l) {
            for (Integer b : r) {
                if (a + b <= distance) {
                    count++;
                }
            }
        }
        List<Integer> list = new ArrayList<>(l.size() + r.size());
        for (Integer a : l) {
            if (a < distance) {
                list.add(a + 1);
            }
        }
        for (Integer a : r) {
            if (a < distance) {
                list.add(a + 1);
            }
        }
        list.add(distance + 1);
        return list;
    }
}
